Exercise 2 (Homework 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages),
coRE)
Classification II: computable languages
For a number p, define \mathcal L_p=\{x \mid M_p(x)\!\downarrow \text{and accepts}\}. For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.
- \{p \mid \mathcal L_p \text{ is finite}\}
- \{p \mid \mathcal L_p \text{ is infinite}\}
- \{p \mid \mathcal L_p \text{ is context-free}\}
- \{p \mid \mathcal L_p \text{ is not context-free}\}